#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//class Solution {
//public:
//    vector<vector<int>> merge(vector<vector<int>>& intervals) {
//        vector<vector<int>> ret;
//        stack<int> st;
//        for (int i = 0; i < intervals.size(); i++)
//        {
//            for (int j = 0; j < intervals[0].size(); j++)
//            {
//                if (st.empty())
//                {
//                    st.push(intervals[i][j]);
//                    continue;
//                }
//                if (intervals[i][j] <= st.top()) st.pop();
//                else st.push(intervals[i][j]);
//            }
//        }
//        vector<int> tmp;
//        while (!st.empty())
//        {
//            tmp.push_back(st.top());
//            st.pop();
//        }
//        reverse(tmp.begin(), tmp.end());
//        vector<int> v;
//        for (auto& e : tmp)
//        {
//            v.push_back(e);
//            if (v.size() == 2)
//            {
//                ret.push_back(v);
//                v.clear();
//            }
//        }
//        return ret;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<vector<int>> arr = { {1, 3},{2, 6},{8, 10},{15, 18} };
//    auto r = s.merge(arr);
//    for (int i = 0; i < r.size(); i++)
//    {
//        for (int j = 0; j < r[0].size(); j++)
//        {
//            cout << r[i][j] << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

//class Solution {
//public:
//    vector<vector<int>> merge(vector<vector<int>>& intervals) {
//        sort(intervals.begin(), intervals.end());
//        vector<vector<int>> ret;
//        for (int i = 0; i < intervals.size();)
//        {
//            int tmp = intervals[i][1];
//            int j = i + 1;
//            while (j < intervals.size() && tmp >= intervals[j][0])
//            {
//                tmp = max(tmp, intervals[j][1]);
//                j++;
//            }
//            ret.push_back({ intervals[i][0], tmp });
//            i = j;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
//        ListNode* ptr = list1;
//        ListNode* cur = ptr;
//        for (int i = 0; i <= b; i++)
//        {
//            list1 = list1->next;
//        }
//        for (int i = 0; i < a - 1; i++)
//        {
//            cur = cur->next;
//        }
//        cur->next = list2;
//        while (cur->next)
//        {
//            cur = cur->next;
//        }
//
//        cur->next = list1;
//        return ptr;
//    }
//};